package easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution_LCS_02 {
    public int halfQuestions(int[] questions) {
        Arrays.sort(questions);
        int[] counts = new int[1001];
        for (int question : questions) {
            counts[question]++;
        }
        List<Integer> list = new ArrayList<>();
        for (int count : counts) {
            if (count > 0) {
                list.add(count);
            }
        }
        Collections.sort(list);
        int sum = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            sum += list.get(i);
            if (sum >= (questions.length >> 1)) {
                return list.size() - i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution_LCS_02 model = new Solution_LCS_02();
        System.out.println(model.halfQuestions(new int[]{2, 1, 6, 2}));
        System.out.println(model.halfQuestions(new int[]{1, 5, 1, 3, 4, 5, 2, 5, 3, 3, 8, 6}));
    }
}
